package algorithm.middle;

import pojo.NestedInteger;

import java.util.*;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: NestedIterator
 * @description: 341. 扁平化嵌套列表迭代器
 * @date 2021/3/2310:31
 * @since V1.0
 * 给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。
 *
 * 列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [[1,1],2,[1,1]]
 * 输出: [1,1,2,1,1]
 * 解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/flatten-nested-list-iterator
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class NestedIterator implements Iterator<Integer> {
    List<Integer> list;
    int i=-1;

    public NestedIterator(List<NestedInteger> nestedList) {
        list = new ArrayList<Integer>();
        fun(nestedList);
    }

    public void fun(List<NestedInteger> nestedList){
        for(NestedInteger item:nestedList){
            if (item.isInteger()){
                list.add(item.getInteger());
            }else {
                fun(item.getList());
            }
        }
    }

    @Override
    public Integer next(){
        return list.get(++i);
    }

    @Override
    public boolean hasNext() {
        return i<list.size()-1;
    }
}
/**
 * 栈 迭代
 * @Param:
 * @Return:
 * @Author: 江岸
 * @Date: 2021/3/23 10:45
 * 算法整体的流程，通过举例说明。假如输入 [1, [2,3]] 。
 *
 * 1. 在构造函数中：栈里面放的应该是 stack = [[2, 3], 1]
 * 2. 在调用 `hasNext()` 方法时，访问栈顶元素是 1，为 int，那么直接返回 true;
 * 3. 然后调用 `next()` 方法，弹出栈顶元素 1；
 * 4. 再调用 `hasNext()` 方法时，访问栈顶元素是 [2,3]，为 list，那么需要摊平，继续放到栈中。
 * 		当前的栈是 stack = [3, 2]
 * 5. 然后调用 `next()` 方法，弹出栈顶元素 2；
 * 6. 然后调用 `next()` 方法，弹出栈顶元素 3；
 * 7. 再调用 `hasNext()` 方法时，栈为空，因此返回 false，迭代器运行结束。
 *
 * 作者：fuxuemingzhu
 * 链接：https://leetcode-cn.com/problems/flatten-nested-list-iterator/solution/fu-xue-ming-zhu-xiang-jie-ti-yi-shu-li-d-n4qa/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class NestedIterator2 implements Iterator<Integer> {
    Deque<NestedInteger> stack = new LinkedList<>();

    public NestedIterator2(List<NestedInteger> nestedList) {
        for(NestedInteger item:nestedList){
            stack.addFirst(item);
        }
    }

    @Override
    public Integer next() {
        return stack.pollLast().getInteger();
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty()){
            NestedInteger pop = stack.peekLast();
            if (pop.isInteger()){
                return true;
            }
            stack.removeLast();
            //摊平入栈 [2,3] -> 3,2
            for (int i=pop.getList().size()-1;i>-1;i--){
                stack.addLast(pop.getList().get(i));
            }
        }
        return false;
    }
}